package com.ljx.QueueStack;

import java.util.Stack;

/**
 * @author 李加喜
 * @Package com.ljx.QueueStack
 * @date 2021-12-10 10:37
 */
//316 去重字母
public class QuChongZiMu {
    public static void main(String[] args) {
        QuChongZiMu mu = new QuChongZiMu();
        System.out.println(mu.removeDuplicateLetters("bcabc"));
    }
    public String removeDuplicateLetters(String s) {
        Stack<Character> stk = new Stack<>();

        // 维护一个计数器记录字符串中字符的数量
        // 因为输入为 ASCII 字符，大小 256 够用了
        int[] count = new int[256];
        for (int i = 0; i < s.length(); i++) {
            // 统计每一个字符出现的次数
            // count统计的是第i个字符出现的次数
            count[s.charAt(i)]++;
        }
//        bcabc
        boolean[] inStack = new boolean[256];
        for (char c : s.toCharArray()) {
            // 每遍历过一个字符，都将对应的计数减一  主要适用于判断是否有重复的数字
            count[c]--;
            // 如果这个值为true 说明存在  如果为False不存在
            if (inStack[c]){
                continue;
            }
            //注意这里是一个栈的循环操作
            while (!stk.isEmpty() && stk.peek() > c) {
                // 若之后不存在栈顶元素了，则停止 pop
                Character character = stk.peek();
                //说明后面已经没有在存在的数据了
                if (count[stk.peek()] == 0) {
                    break;
                }
                // 若之后还有，则可以 pop
                inStack[stk.pop()] = false;
            }
            stk.push(c);
            // 说明这个字符存的  用于判断的时候进行使用的
            inStack[c] = true;
        }

        StringBuilder sb = new StringBuilder();
        while (!stk.empty()) {
            sb.append(stk.pop());
        }
        return sb.reverse().toString();
    }
}
